SEC 2
効率的暗号化の標準(Standards for Efficient Cryptography)
SEC 2: 推奨楕円曲線ドメインパラメータ
Certicom Research
連絡先: Daniel R. L. Brown (dbrown@certicom.com)
2010年1月27日
バージョン 2.0
1 はじめに Introduction
1.1 概要 Overview
この文書では、SEC 1 SEC 1 や、ANSI X9.62 X9.62、ANSI X9.63 X9.63、IEEE 1363 1363、IEEE 1363a 1363A などの他の ECC 標準の実装者が使用するために、一般的に必要なセキュリティ レベルでの楕円曲線ドメイン パラメーターの例をリストします。 実装者は、相互運用可能な ECC ベースのソリューションの展開を促進するために、ECC ベースの製品を展開するときに、このドキュメントにリストされているパラメータの中からパラメータを選択することを強くお勧めします。
1.2 準拠 Compliance
実装は、推奨パラメータの一部が実装に含まれる楕円曲線暗号に基づく暗号スキームで使用される場合に限り、この文書で指定されている推奨パラメータへの準拠を主張できます。
この文書に準拠することを選択した実装は、通常、その関連文書である SEC 1 SEC 1 にも準拠することを選択することが想定されます。 これは、実装者がこの文書への準拠をチェックできるように、検証システムを利用できるようにすることを目的としています。詳細については、SECG Web サイト (https://www.secg.org ) を参照してください。 1.3 ドキュメントの進化 Document Evolution
この文書は、暗号化の進歩に合わせて最新の状態に保たれるよう、5 年ごとに見直されます。したがって、次回の見直しは 2015 年 2 月に予定されています。
Standards for Efficient Cryptography Group が必要と判断した場合、追加の断続的なレビューも随時実行される場合があります。
1.4 知的財産 Intellectual Property
この文書に準拠するには、特許権の対象となる発明の使用が必要となる可能性があることに読者の注意を促します。この文書の発行によって、この請求項またはそれに関連する特許権の有効性に関していかなる立場も取られません。特許所有者は、かかるライセンスの取得を希望する出願人に対して、公正、合理的かつ無差別の条件に基づいて、これらの権利に基づくライセンスを付与する意向の声明を SECG に提出している可能性があります。追加の詳細は、特許所有者および SECG の Web サイト (https://www.secg.org ) から入手できます。 1.5 組織
この文書は次のように構成されています。
この文書の本文は、推奨される楕円曲線ドメイン パラメーターの仕様に焦点を当てています。セクション 2 では $ \mathbb{F}_p に関する推奨楕円曲線ドメイン パラメーターについて説明し、セクション 3 では $ \mathbb{F}_{2^m} に関する推奨楕円曲線ドメイン パラメーターについて説明します。
この文書の付録には、追加の関連資料が含まれています。付録 A では、実装でパラメータを識別するために使用する参照 ASN.1 構文を提供します。付録 B には、この文書で引用されている参考文献がリストされています。
2 $ \mathbb{F}_p に対する推奨される楕円曲線領域 パラメーター
この節では、この文書で推奨される $ \mathbb{F}_p 上の楕円曲線領域パラメータを規定する。
この節は次のように構成されています。最初の 2.1節では、$ \mathbb{F}_p 上の推奨パラメータの関連特性について説明します。次に 2.2節で $ \mathbb{F}_p に対する推奨 192 ビット楕円曲線領域 パラメータを指定し、2.3節 で $ \mathbb{F}_p に対する推奨 224 ビット楕円曲線領域 パラメータを指定、2.4節 で $ \mathbb{F}_p に対する推奨 256 ビット楕円曲線領域 パラメータを指定、2.5節 で $ \mathbb{F}_p に対する推奨 384 ビット楕円曲線領域 パラメータを指定、2.6節で推奨 521 ビット楕円曲線領域 パラメータを指定します。
2.1 $ \mathbb{F}_p 上の楕円曲線領域パラメータの性質
SEC 1 SEC 1 に従い、$ \mathbb{F}_p 上の楕円曲線領域パラメータは、以下の6組で構成される。 $ T = (p, a, b, G, n, h)
有限体 $ \mathbb{F}_p を表す整数 p、方程式 $ E(\mathbb{F}_p) を定義する2つの要素 $ a,b\in\mathbb{F}_p から構成される。
$ E : y^2 ≡ x^3 + a.x + b (\bmod p)
$ E(\mathbb{F}_p) 上の基点 $ G = (x_G, y_G) 、$ G の位数を表す素数 n、そして余因子(cofactor) $ h = \#E(\mathbb{F}_p)/n を表す整数 h。
本文書において楕円曲線領域パラメータを指定する場合、この6組の各要素は、SEC 1 SEC 1 で規定された規則に従って変換されたオクテット文字列として表される。 SEC 1 SEC 1 に再び従うと、$ \mathbb{F}_p 上の楕円曲線領域パラメータは以下を満たす必要がある。 $ \lceil log_2 p \rceil \in \{192, 224, 256, 384, 521\}
この制約は、実装者が一般的に要求されるセキュリティレベルを提供できるようにしつつ、相互運用性を促進するために設計されている。$ \lceil log_2 p \rceil = 2t を満たす $ \mathbb{F}_p 上の楕円曲線領域パラメータは約 t ビットのセキュリティを提供することを思い出すとよい。これは、関連する楕円曲線上の対数問題を解くには約 $ 2^t 回の演算が必要であると考えられることを意味する。
ここでは、SEC 1 で許容される各サイズについて、推奨される楕円曲線領域パラメータが提供される。
$ \mathbb{F}_p 上の推奨されるすべての楕円曲線領域パラメータは、体の順序$ p に特殊形式の素数を使用する。これらの特殊形式の素数は、Nat99 で説明されているような特に効率的な実装を容易にする。 $ \mathbb{F}_p 上の楕円曲線領域パラメータ（体の位数 p にランダム素数を使用するもの）は、商用利用の需要が増加すれば、後日追加される可能性があります。 各セキュリティレベルで提供される$ \mathbb{F}_p 上の楕円曲線領域パラメータは、通常、2 つの異なるタイプのパラメータの例で構成されます。1 つは Koblitz 曲線に関連付けられたパラメータで、もう 1 つは検証可能にランダムに選択されたパラメータです。ただし、輸出強度および極めて高い強度では、検証可能にランダムなパラメータのみが提供されます。
コブリッツ曲線(Koblitz curve)に関連付けられたパラメータは、特に効率的な実装が可能です。Koblitz曲線という名称は、a, b ∈ {0, 1} となる $ \mathbb{F}_{2^m} 上の 2 値異常曲線を記述する際に最もよく知られています Kob92。ここでは、効率的に計算可能な自己準同型性を持つ $ \mathbb{F}_p 上の曲線も指すように一般化されています GLV01。コブリッツ曲線に関連付けられた推奨パラメータは、素数位数曲線が見つかるまで、効率的に計算可能な自己準同型性を持つパラメータを繰り返し選択することによって選択されました。 検証可能ランダムパラメータは、いくつかの追加の保守的な特徴を提供します。これらのパラメータは、ANSI X9.62 X9.62 で規定されている SHA-1 を使用してシードから選択されます。このプロセスにより、パラメータが事前に決定できないことが保証されます。したがって、パラメータが将来の特殊目的の攻撃に対して脆弱になる可能性は極めて低く、パラメータの生成時にトラップドアが配置されることはありません。楕円曲線の領域パラメータが検証可能にランダムに選択される場合、パラメータ生成に用いられるシードSは、オプションでパラメータと共に保存され、ユーザがパラメータが検証可能にランダムに選択されたことを検証できるようにしてもよい。 ここで検証可能にランダムなパラメータは、関連する楕円曲線が素数位数となるように、または関連する楕円曲線上の点のスカラー倍算をモンゴメリ法 Mon87 を用いて高速化できるように選択された。推奨される検証可能ランダムなパラメータは、適切なパラメータが見つかるまで、ランダムシードを繰り返し選択し、対応する曲線上の点の数を数えることによって選択された。典型的には、パラメータは$ a = p − 3 となるように選択される。これは、そのようなパラメータは効率的な実装を可能にするためである。与えられたpに対して、$ \mathbb{F}_p 上の楕円曲線の同型類の約半分は、$ a = p−3 となる曲線を含む。 $ \mathbb{F}_p上の楕円曲線領域パラメータの選択に関する詳細なガイダンスについては、SEC 1 SEC 1 を参照のこと。 table:Fp上の推奨楕円曲線領域パラメータの特性
パラメータ 節 強度 Size RSA/DSA Koblitz
またはランダム(r)
secp192k1 2.2.1 96 192 1536 k
secp192r1 2.2.2 96 192 1536 r
secp224k1 2.3.1 112 224 2048 k
secp224r1 2.3.2 112 224 2048 r
secp256k1 2.4.1 128 256 3072 k
secp256r1 2.4.2 128 256 3072 r
secp384r1 2.5.1 192 384 7680 r
secp521r1 2.6.1 256 521 15360 r
表1: $ \mathbb{F}_p 上の推奨楕円曲線領域パラメータの特性
$ \mathbb{F}_p 上の推奨楕円曲線領域パラメータには、識別を容易にするためにニックネームが付けられています。ニックネームは次のように選ばれました。それぞれの名前は、「効率的な暗号化の標準」を表す sec で始まり、$ \mathbb{F}_p 上のパラメータを表す p が続き、フィールドサイズ p のビット長を表す数字が続き、Koblitz曲線に関連付けられたパラメータを表す k または検証可能ランダムパラメータを表す r が続き、シーケンス番号が続きます。
表 1 は、$ \mathbb{F}_p 上の推奨楕円曲線領域パラメータの主要な特性をまとめたものです。
表 1 では、情報が次のように表されています。「パラメータ」というラベルの列には、楕円曲線領域パラメータのニックネームが示されています。「節」というラベルの列は、このドキュメント内でパラメータが指定されている節を示しています。「強度」というラベルの列には、パラメータが提供するセキュリティのビット数の概算が示されています。「Size」というラベルの列には、フィールド順序のビット長が示されています。 「RSA/DSA」というラベルの付いた列は、同等の強度におけるRSAまたはDSA係数のおおよそのサイズを示しています。（楕円曲線ドメインパラメータの強度に関する正確な技術的ガイダンスについては、SEC 1 SEC 1を参照してください。）最後に、「Koblitzまたはランダム」というラベルの付いた列は、パラメータがKoblitz曲線に関連付けられているかどうか（「k」）と、検証可能なランダムに選択されたかどうか（「r」）を示しています。 table:表2 Fp上の推奨楕円曲線領域パラメータの状況
パラメータ 節 ANSI X9.62 ANSI X9.63 echeck IEEE P1363 IPSec NIST WAP
secp192k1 2.2.1 c c c c - - c
secp192r1 2.2.2 r r c c r r c
secp224k1 2.3.1 c c c c - - c
secp224r1 2.3.2 r r c c r r c
secp256k1 2.4.1 c c c c - - c
secp256r1 2.4.2 r r c c r r c
secp384r1 2.5.1 c r c c r r c
secp521r1 2.6.1 r r c c r r c
表2は、$ \mathbb{F}_p 上の推奨楕円曲線領域パラメータについて、他の標準との整合性の観点から現状をまとめたものである。
表2では、以下の情報が提示されている。「パラメータ」の列は、楕円曲線領域パラメータのニックネームを示している。「セクション」の列は、パラメータが規定されているこの文書のセクションを示している。残りの列は、楕円曲線暗号に基づくメカニズムを規定するさまざまな他の標準に関するパラメータのステータスを示します。「ANSI X9.62」は ANSI X9.62 標準 X9.62、「ANSI X9.63」は ANSI X9.63 標準 X9.63、「echeck」は FSML 標準の草案 Fin99、「IEEE P1363」は IEEE 1363 標準 1363、「IPSec」は IETF の IPSec ワーキング グループに提出された ECC に関する最近のインターネット ドラフト Int06、「NIST」は米国政府によって最近リリースされた推奨パラメータのリスト Nat99、「WAP」は Wireless Application Forum の WTLS 標準 WTLS を指します。これらの列において、「-」は標準に準拠していないパラメータ、「c」は標準に準拠しているパラメータ、「r」は標準で明示的に推奨されているパラメータを示します。 ANSI X9.62は更新されていることに注意してください。更新されたANSI X9.62 X9.62 で推奨されているパラメータセットは、この文書で推奨されているパラメータセットのサブセットです。 2.2 $ \mathbb{F}_p 上の推奨される 192 ビット楕円曲線領域パラメータ
このセクションでは、この文書で推奨される 2 つの 192 ビット楕円曲線領域パラメータ、すなわち Koblitz 曲線に関連付けられたパラメータ secp192k1 と、検証可能ランダムパラメータ secp192r1 を規定します。
2.2.1 セクションでは楕円曲線領域パラメータ secp192k1 を規定し、2.2.2 セクションでは楕円曲線領域パラメータ secp192r1 を規定します。
2.2.1 推奨パラメータ secp192k1
Koblitz 曲線 secp192k1 に関連付けられた $ \mathbb{F}_p 上の楕円曲線領域パラメータは、6 組 T = (p, a, b, G, n, h) で規定されます。ここで、有限体 $ \mathbb{F}_p は次のように定義されます。
$ p={\tt FFFFFFFF\:FFFFFFFF\:FFFFFFFF\:FFFFFFFF\:FFFFFFFE\:FFFFEE37}
$ = 2^{192}-2^{32}-2^{12}-2^8-2^7-2^6-2^3-1
曲線 $ E: y^2=x^3+ax+b ($ \mathbb{F}_p 上)の定義は
$ a= {\tt 00000000\:00000000\:00000000\:00000000\:00000000\:00000000}
$ b={\tt00000000\:00000000\:00000000\:00000000\:00000000\:00000003}
圧縮された形式の基点 G は次のとおりです。
$ G= {\tt\qquad\quad\:03\:DB4FF10E\:C057E9AE\:26B07D02\:80B7F434\:1DA5D1B1\:EAE06C7D}
圧縮されていない形式では次のようになります。
$ G= {\tt\qquad\quad\:04\:DB4FF10E\:C057E9AE\:26B07D02\:80B7F434\:1DA5D1B1\:EAE06C7D}
$ {\tt\quad9B2F2F6D\:9C5628A7\:844163D0\:15BE8634\:4082AA88\:D95E2F9D}
最終的に G の位数 n と余因子は次のようになります。
$ n= {\tt FFFFFFFF\:FFFFFFFF\:FFFFFFFE\:26F2FC17\:0F69466A\:74FEFD8D}
$ h = {\tt\quad\qquad 01}
3 $ \mathbb{F}_{2^m} 上の推奨楕円曲線領域パラメータ
この節では、この文書で推奨される $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータを規定する。
この節は以下のように構成されている。まず、3.1節では $ \mathbb{F}_{2^m}上の推奨パラメータの関連特性について述べる。次に、3.2節では $ \mathbb{F}_{2^m}上の推奨163ビット楕円曲線領域パラメータを規定する。3.3節では $ \mathbb{F}_{2^m}上の推奨233ビット楕円曲線領域パラメータを規定する。3.4節では $ \mathbb{F}_{2^m}上の推奨239ビット楕円曲線領域パラメータを規定する。3.5節では $ \mathbb{F}_{2^m}上の推奨283ビット楕円曲線領域パラメータを規定する。3.6節では $ \mathbb{F}_{2^m}上の推奨409ビット楕円曲線領域パラメータを規定する。3.7節では $ \mathbb{F}_{2^m}上の推奨571ビット楕円曲線領域パラメータを規定する。
3.1 $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータの性質
SEC 1 SEC 1 に従い、$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータは7組である。 $ T = (m, f (x), a, b, G, n, h)
これは、有限体 $ \mathbb{F}_{2^m} を表す整数 $ m 、$ \mathbb{F}_{2^m} の多項式基底表現を表す $ m 次既約二項式$ f (x) 、次式で定義される楕円曲線 $ E(\mathbb{F}_{2^m}) を表す2つの元 $ a,b\in\mathbb{F}_{2^m} からなる。
$ E:y^2+x.y=x^3+a.x^2+b \;in\; \mathbb{F}_{2^m}
$ E(\mathbb{F}_{2^m}) 上の基点 $ G = (x_G, y_G) 、G の位数である素数 $ n 、そして余因子$ h = \#E(\mathbb{F}_{2^m} )/n である整数 h から構成される。
この文書において$ \mathbb{F}_{2^m} 上の楕円曲線領域パラメータを規定する場合、mは整数として直接表現され、$ f(x) は多項式として直接表現され、残りの要素はSEC 1 SEC 1 で規定された規則に従って変換されたオクテット文字列として表現される。 SEC 1 SEC 1 に再び従うと、$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータは以下の式を満たす必要がある。 $ m \in \{163, 233, 239, 283, 409, 571\}
さらに、$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータは、以下の表3に列挙する縮約多項式を使用しなければならない。
この制限は、実装者が一般的に要求されるセキュリティレベルで効率的な実装を提供できるようにしつつ、相互運用性を促進するために設計されている。
ここでは、SEC 1 で許可されている各サイズで、推奨される楕円曲線ドメインパラメータが提供されます。
各セキュリティレベルで提供される $ \mathbb{F}_{2^m} 上の楕円曲線ドメインパラメータは、通常、2 つの異なるタイプのパラメータの例で構成されます。1 つは Koblitz 曲線に関連付けられたパラメータであり、もう 1 つは検証可能にランダムに選択されたパラメータです。ただし、エクスポート強度では検証可能にランダムなパラメータのみが提供されます。
table:表3 F_2^mの表現
Field 縮小多項式
F_2^163 f(x) = x^163+x^7+x^6+x^3+1
F_2^233 f(x) = x^233+x^74+1
F_2^239 f(x) = x^239+x^36+1 or x^239+x^158+1
F_2^283 f(x) = x^283+x^12+x^7+x^5+1
F_2^409 f(x) = x^409+x^87+1
F_2^571 f(x) = x^571+x^10+x^5+x^2+1
Koblitz曲線に関連付けられたパラメータは、特に効率的な実装が可能です。$ \mathbb{F}_{2^m} 上のKoblitz曲線は、$ a, b \in \{0, 1\} となる二値異常曲線です Kob92。 検証可能ランダムパラメータは、いくつかの追加の保守的な特徴を備えています。これらのパラメータは、ANSI X9.62 X9.62 で規定されている SHA-1 を用いてシードから選択されます。このプロセスにより、パラメータが事前に決定されないことが保証されます。したがって、これらのパラメータは将来の特殊目的の攻撃に対して脆弱になる可能性は極めて低く、生成時にパラメータにトラップドアが仕掛けられることはありません。楕円曲線ドメインパラメータが検証可能ランダムに選択される場合、パラメータの生成に使用されたシード S をオプションでパラメータと共に保存し、ユーザーがパラメータが検証可能ランダムに選択されたことを検証できるようにすることができます。 推奨される検証可能ランダムパラメータは、適切なパラメータが見つかるまで、ランダムシードを繰り返し選択し、Schoof アルゴリズムを用いて対応する曲線上の点を数えることによって選択されました。パラメータは、a がランダムか a = 1 となるように選択された。与えられた m に対して、 $ \mathbb{F}_{2^m}上の楕円曲線の同型類の約半数は、a = 1 となる曲線を含む。
$ \mathbb{F}_{2^m}上の楕円曲線領域パラメータの選択に関する詳細なガイダンスについては、SEC 1 SEC 1 を参照のこと。 $ \mathbb{F}_{2^m}上の楕円曲線領域パラメータの例には、容易に識別できるようにニックネームが付けられている。ニックネームは次のように選択された。それぞれの名前は、「効率的暗号化の標準(Standards for Efficient Cryptography)」を表す sec で始まり、次に $ \mathbb{F}_{2^m}上のパラメータを表す t が続き、次に体のサイズ m を表す数字が続き、次にKoblitz曲線に関連付けられたパラメータを表す k または検証可能ランダムパラメータを表す r が続き、最後にシーケンス番号が続く。
表 4 は、 $ \mathbb{F}_{2^m}上の推奨される楕円曲線領域パラメータの主要な特性をまとめたものである。
表 4 の情報は次のように表される。 「パラメータ」という列には、楕円曲線ドメインパラメータのニックネームが示されています。「セクション」という列は、このドキュメントのどのセクションのパラメータが指定されているかを示しています。「強度」という列には、パラメータが提供するセキュリティのビット数の概算が示されています。「サイズ」という列には、フィールドのサイズ m が示されています。「RSA/DSA」という列には、同等の強度における RSA または DSA 係数の概算が示されています。（楕円曲線ドメインパラメータの強度に関する正確な技術的ガイダンスについては、SEC 1 SEC 1 を参照してください。）最後に、「コブリッツまたはランダム」という列には、パラメータがコブリッツ曲線に関連付けられているかどうか（「k」）と、検証可能なランダムに選択されたかどうか（「r」）が示されています。 table:表4: F_2^m上の推奨楕円曲線領域パラメータの特性
ぱらめーた 節 強度 サイズ RSA/DSA Koblitz
Section Strength or random
sect163k1 3.2.1 80 163 1024 k
sect163r1 3.2.2 80 163 1024 r
sect163r2 3.2.3 80 163 1024 r
sect233k1 3.3.1 112 233 2240 k
sect233r1 3.3.2 112 233 2240 r
sect239k1 3.4.1 115 239 2304 k
sect283k1 3.5.1 128 283 3456 k
sect283r1 3.5.2 128 283 3456 r
sect409k1 3.6.1 192 409 7680 k
sect409r1 3.6.2 192 409 7680 r
sect571k1 3.7.1 256 571 15360 k
sect571r1 3.7.2 256 571 15360 r
table:表5：F2mにおける推奨楕円曲線領域パラメータの現状